package leetcode_链表;

import general_class.ListNode;

/**
 * 25. K 个一组翻转链表
 * 算法：链表
 *
 * @author yzh
 * @version 1.0
 * @date 2022/3/21 22:39
 */
public class _25 {

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode ans = new ListNode();
        ans.next = head;
        ListNode pre = ans, end = ans;
        while (end.next != null) {
            for (int i = 0; i < k && end != null; i++) end = end.next;
            if (end == null) break;
            ListNode start = pre.next;
            ListNode next = end.next;
            end.next = null;
            pre.next = reverse(start);
            start.next = next;
            pre = start;
            end = pre;
        }
        return ans.next;
    }

    private ListNode reverse(ListNode node) {
        ListNode pre = null, cur = node;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public ListNode reverseKGroup_202221210(ListNode head, int k) {
        int sum = 0;
        ListNode cur = head;
        while (cur != null) {
            ++sum;
            cur = cur.next;
        }
        ListNode dummy = new ListNode(-1, head), p0 = dummy, pre = null, next = null;
        cur = dummy.next;
        while (sum >= k) {
            for (int i = 0; i < k; i++) {
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            next = p0.next;
            p0.next.next = cur;
            p0.next = pre;
            p0 = next;
            sum -= k;
        }
        return dummy.next;
    }

    public ListNode reverseKGroup_20240111(ListNode head, int k) {
        ListNode dummy = new ListNode(), cur = dummy, end, newHead, next;
        while (true) {
            end = head;
            int i = 0;
            for (; i < k - 1 && end != null; i++) end = end.next;
            if (i != k - 1 || end == null) break;
            next = end.next;
            end.next = null;
            newHead = reverse(head);
            cur.next = newHead;
            head.next = next;
            cur = head;
            head = next;
        }
        return dummy.next;
    }

}
